//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例： 
//
// 输入：n = 3
//输出：[
//       "((()))",
//       "(()())",
//       "(())()",
//       "()(())",
//       "()()()"
//     ]
// 
// Related Topics 字符串 回溯算法


package leetcode.d_1_99;

import java.util.ArrayList;
import java.util.List;

//Java：括号生成
public class P22GenerateParentheses{
    public static void main(String[] args) {
        Solution solution = new P22GenerateParentheses().new Solution();
        // TO TEST
        List<String> list = solution.generateParenthesis(3);
        System.out.println(list);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<String> res;
        public List<String> generateParenthesis(int n) {
            res = new ArrayList<>();
            generate(0, 0, n, "");
            return res;
        }

        private void generate(int left, int right, int n, String s) {
            if (left == n && right == n){
                res.add(s);
                return;
            }
            if (left < n){
                generate(left + 1, right, n, s + "(");
            }
            if (right < left){
                generate(left, right + 1, n, s + ")");
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}